package primalgorithms.math;

public class _02CountPrimes {
    public static int countPrimes(int n) {
        //素数筛
        boolean[] ifNotPrime = new boolean[n]; //若为true，则不是素数
        int res = 0;
        //从2开始，将所有质数的x倍全部标记为合数,一直标记到根号n
        for (int i = 2;i < n;i++){
            if (ifNotPrime[i]){
                continue;
            }
            res++;
            //注意j从当前素数的2倍开始筛选
            //但这样势必会造成重复筛查的问题：
            //比如排查7时，for循环给ifNotPrime[14]赋值为true，但实际上它已经是true了
            for (int j = i+i;j < n;j += i){
                ifNotPrime[j] = true;
            }
        }
        return res;

        /**     该方案更加直观
         *          // 初始化全部为质数
         *         boolean[] isPrimeArray = new boolean[n];
         *         Arrays.fill(isPrimeArray,true);
         *         // 从2开始，将所有质数的x倍全部标记为合数,一直标记到根号n
         *         for (int i = 2; i * i < n; i++) {
         *             if(isPrimeArray[i]){
         *                 int x = i;
         *                 while (i*x < n){
         *                     isPrimeArray[i*x] = false;
         *                     x++;
         *                 }
         *             }
         *         }
         *         // 从 2 开始计数
         *         int result = 0;
         *         for (int i = 2; i < n; i++) {
         *             if(isPrimeArray[i]){
         *                 result++;
         *             }
         *         }
         *         return result;
         */
    }
}
